/*  -*- mode: c++; coding: utf-8; c-file-style: "stroustrup"; -*-

    Copyright 2008 Asier Aguirre <asier.aguirre@gmail.com>
    This file is part of Intromit.

    Intromit is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Intromit is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Intromit.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "metadata.hh"
#include "dwarf.hh"
#include "file_mng.hh"
#include "source.hh"
#include "config.hh"
#include "elf.hh"
#include "intromit.hh"

#include <dlfcn.h>
#include <string.h>
#include <errno.h>
#include <ctype.h>

// DEFINES
#define INC_INFO_ARRAY        32
#define INC_INFO             256
#define INC_NAMES            128
#define INC_TYPEDEF         1024
#define INC_PATTERN         1024
#define INC_FILE               8
#define INC_MODULES            8
#define BIG_LINE      0x7fffffff
#define N_BUFFER            2048
#define MAX_SUBSTS            32

#define CONFIG_FILE               STR(PREFIX)"/etc/intromit/metadata.cfg"

#define STR_SELECTION             "selection"
#define STR_EMPTY_SELECTION       "emptyselection"
#define STR_ADD_RULE              "addrule"
#define STR_DEL_RULE              "delrule"
#define STR_FILE                  "file"
#define STR_NAME                  "name"
#define STR_COMMENT               "comment"
#define STR_TAG                   "tag"
#define STR_ADD_CLASS             "addclass"
#define STR_DEL_CLASS             "delclass"

#define STR_MATCHING              "matching"
#define STR_TYPEDEF               "typedef"
#define STR_PATTERN               "pattern"
#define STR_COMPONENT             "component"
#define STR_ENCODING              "encoding"
#define STR_ATTR                  "attr"
#define STR_SIZE                  "bytesize"
#define STR_TYPE                  "type"
#define STR_TYPE_RECUR            "typerecur"

#define STR_GENERATION            "generation"
#define STR_PASS                  "pass"
#define STR_MODULE                "module"
#define STR_FUNC_PREFIX           "funcprefix"
#define STR_REPETITIONS           "repetitions"

#define STR_PRIVATE_MEMBER_MARK   "privatemembersmark"
#define STR_STATUS_MEMBER_MARK    "statusmembersmark"
#define STR_PRIVATE_METHOD_MARK   "privatemethodsmark"
#define STR_INTERFACE_METHOD_MARK "interfacemethodsmark"

#define STR_ATTR_PREFIX           "docattrprefix"
#define STR_ATTR_SEPARATOR        "docattrseparator"
#define STR_ATTR_START            "docattrblockstart"
#define STR_ATTR_END              "docattrblockend"
#define STR_ATTR_NOT              "docattrnot"
#define STR_ATTR_SELECTION        "docattrselection"
#define STR_ATTR_OFFLINE          "docattroffline"

static const char *md_func_keys[MD_FUNC_LAST]=
{
    "initfunc", "finishfunc", "typerecurfunc", "nextfunc", "downfunc", "upfunc", "initpassfunc", "finishpassfunc"
};

CLASS_INIT(metadata); // METADATA CLASS

metadata::metadata()
{
    CLASS_CTOR(metadata);
    ctor();
}

metadata::~metadata()
{
    CLASS_DTOR(metadata);
    dtor();
}

void metadata::ctor()
{
    dw=NULL;
    src=NULL;
    cfg=NULL;

    // marks
    for(int i=0; i<MD_MARK_LAST; i++) mark[i]=NULL;

    // functions
    for(int i=0; i<MD_FUNC_LAST; i++) functions[i]=NULL;

    // output files
    util::ctor_vector(out, n_out, max_out);

    // modules
    util::ctor_vector(mod, n_mod, max_mod);

    // prefix
    prefix=NULL;
    n_prefix=0;

    // user data
    user_data=NULL;
    pass=repetition=-1;

    // options
    opts=NULL;

    // delcarations gcc warning
    gcc_need_to_find_decls=0;
}

void metadata::dtor()
{
    if(dw) {delete dw; dw=NULL;}
    if(src) {delete src; src=NULL;}
    if(cfg) {delete cfg; cfg=NULL;}

    // marks
    for(int i=0; i<MD_MARK_LAST; i++) if(mark[i]) mark[i]=(char*)realloc(mark[i], 0);

    // functions
    reset_functions();

    // output files
    util::dtor_vector(out, n_out, max_out);

    // modules
    util::dtor_vector(mod, n_mod, max_mod);

    // prefix
    if(prefix) prefix=(char*)realloc(prefix, 0);
    n_prefix=0;

    // user data
    user_data=NULL;
}

void metadata::set_mark(metadata_marks id, char *m)
{
    if(mark[id]) mark[id]=(char*)realloc(mark[id], 0);
    if(m) mark[id]=strdup(m);
}

void metadata::set_function(metadata_funcs id, char *funcname)
{
    if(functions[id]) functions[id]=(char*)realloc(functions[id], 0);
    if(funcname) functions[id]=strdup(funcname);
}

void metadata::reset_functions()
{
    for(int i=0; i<MD_FUNC_LAST; i++) if(functions[i]) functions[i]=(char*)realloc(functions[i], 0);
}

void metadata::dump_tree(const char *str, const char *filename)
{
    FILE *arch=stdout;
    if(filename && !(arch=fopen(filename, "w"))) MSG_R("%s: dump tree: %s", filename, strerror(errno));

    if(arch==stdout) fflush(stderr);
    fprintf(arch, "==== BEGIN: %s ====\n", str);
    dw->analyze_dump_arch(arch, -1/*from*/, 0/*init_level*/, -1/*child*/, 2/*type*/);
    fprintf(arch, "==== END: %s ====\n", str);
    if(arch==stdout) fflush(stdout); else fclose(arch);
}

int metadata::generate(command_options *opts_)
{
    // options
    opts=opts_;

    // config (analyze file)
    char *config_file=opts->config_file?opts->config_file:const_cast<char*>(CONFIG_FILE);
    if(!cfg) cfg=new config;
    cfg->init_pairs();
    if(!cfg->init_filename(config_file)) return 0;
    if(opts->dbg_config_file) cfg->dump(opts->dbg_config_file);

    // declarations gcc warning
    if(!opts->verbo) gcc_need_to_find_decls++;

    // from selection section, extract marks and activate attribute specification params in source obj
    if(!selection_get_marks()) MSG("error with selection block in config file, continuing anyway");

    int dev=1;
    for(int i_elf_list=0; i_elf_list<opts->n_elf_list; i_elf_list++)
    {
	// open dwarf info
	if(!dw) dw=new dwarf;
	if(!dw->analyze_begin(opts->elf_list[i_elf_list])) MSG_R0("dwarf::analyze: input file error");
	if(opts->verbo>1) {MSG_NEOL("dwarf-elf: "); dw->analyze_dump_stats();}
	if(opts->dbg_dwarf_bases) dump_tree("Complete dwarf base tree", "/tmp/dwarf_1_complete.txt");

	// remove duplicates
	if(!dw->analyze_remove_duplicates()) MSG_R0("cannot remove dwarf-metadata duplicates");
	if(opts->verbo>1) {MSG_NEOL("compacted: "); dw->analyze_dump_stats();}
	if(opts->dbg_dwarf_bases) dump_tree("W/O duplicates dwarf base tree", "/tmp/dwarf_2_wo_duplicates.txt");

	// source (create and add feature lines)
	if(!src) src=new source;
	src->init(dw->get_doc(),
		  mark[MD_MARK_ATTR_PREFIX], mark[MD_MARK_ATTR_SEPARATOR],
		  mark[MD_MARK_ATTR_START], mark[MD_MARK_ATTR_END], mark[MD_MARK_ATTR_NOT],
		  mark[MD_MARK_ATTR_OFFLINE]);
	for(int i=0; i<dw->analyze_get_n_base(); i++)
	{
	    dwarf_base *b=dw->analyze_get_base(i);
	    if(b->i_source>=0 && !b->bit.artificial) src->add_feature_line(b->i_source, b->line);
	}

	// resolve imported_declarations
	if(!dw->analyze_resolve_imported_declarations_and_typedefs()) MSG_R0("cannot resolve imported declarations");
	if(opts->verbo>1) {MSG_NEOL("importDcl: "); dw->analyze_dump_stats();}
	if(opts->dbg_dwarf_bases) dump_tree("ImpDecls and typedefs resolved; dwarf base tree", "/tmp/dwarf_3_imports.txt");

	// extract attributes
	for(int i=0; i<dw->analyze_get_n_base(); i++)
	{
	    dwarf_base *b=dw->analyze_get_base(i);
	    if(b->i_source>=0 && !b->bit.artificial)
		b->i_attr=dw->get_doc()->search_add_string(
		    src->attributes(b->i_source, b->line,
				    b->i_name<0?NULL:dw->get_doc()->string(b->i_namespace),
				    dw->get_doc()->string(b->i_name)));
	}
	if(opts->dbg_dwarf_bases) dump_tree("Extraction of attributes", "/tmp/dwarf_4_attributes.txt");

	// dump offline attributes (command line dbg_off_attrs)
	if(opts->dbg_off_attrs) src->dump_offline_attrs(opts->dbg_off_attrs);

	// metadata-info selection
	if(!selection()) MSG("selection of metadata info failed, continuing anyway!");
	if(opts->dbg_dwarf_bases) dump_selection("/tmp/dwarf_5_selection.txt");

	// extract metadata (matching)
	util::ctor_vector(pattern, n_pattern, max_pattern);
	if(!pattern_extract_from_cfg()) {dev=0; MSG("extracting matching patterns");}
	if(opts->dbg_pattern) dump_patterns(opts->dbg_pattern);
	if(dev && !pattern_check()) {dev=0; MSG("checking patterns");}
	if(dev && !pattern_match_metadata()) {dev=0; MSG("extracting metadata");}
	util::dtor_vector(pattern, n_pattern, max_pattern);
	if(opts->dbg_dwarf_bases) dump_tree("Matched dwarf base tree", "/tmp/dwarf_6_matched.txt");

	// remove matched types that are unmanageable (like void*)
	if(dev && !pattern_unmatch_impossible_metadata(opts->verbo, opts->unmanageable))
	    {dev=0; MSG("unmatching impossible metadata");}
	if(opts->dbg_dwarf_bases) dump_tree("Matched dwarf base tree", "/tmp/dwarf_7_unmatched_unmanageable.txt");

	// remove non matched
	if(!dw->analyze_remove_non_matched()) MSG_R0("cannot remove dwarf-metadata non-matched");
	string_index *old_doc;
	if(!(old_doc=dw->analyze_reindex_doc())) MSG_R0("reindexing doc");
	if(!src->reindex(dw->get_doc())) MSG_R0("reindexing src");
	delete old_doc;
	if(opts->verbo>1) {MSG_NEOL("matched:   "); dw->analyze_dump_stats();}
	if(opts->dbg_dwarf_bases) dump_tree("Matched and removed dwarf base tree", "/tmp/dwarf_8_non_match_removed.txt");

	// check and complete linkage names of subprograms
	if(!dw->analyze_check_complete_linkage(opts->verbo, opts->unresolubled, opts->dbg_symbols))
	{
	    if(opts->verbo>0) MSG("%s: some symbols will be lost", opts->elf_list[i_elf_list]);

	    // remove non-matched again
	    if(!dw->analyze_remove_non_matched()) MSG_R0("cannot remove dwarf-metadata non-matched");
	    if(!(old_doc=dw->analyze_reindex_doc())) MSG_R0("reindexing doc");
	    if(!src->reindex(dw->get_doc())) MSG_R0("reindexing src");
	    delete old_doc;
	    if(opts->verbo>1) {MSG_NEOL("post-link: "); dw->analyze_dump_stats();}
	    if(opts->dbg_dwarf_bases) dump_tree("Post linkage base tree", "/tmp/dwarf_9_linkage.txt");
	}

	// generation
	if(dw->analyze_get_n_base() &&
	   !generate_output(opts->output, opts->elf_list[i_elf_list], opts->modules_path, opts->verbo))
	    MSG_R0("error: generating output phase");

	// exit
	if(!dw->analyze_end()) MSG_R0("cannot finish dwarf::analyze");
    }
    return dev;
}

bool metadata::selection_get_marks()
{
    // search selection section
    int ini, end;
    if(!cfg->search_block((char*)STR_SELECTION, NULL, &ini, &end)) {ini=0; end=-1;} else ini++;

    // extract marks and make a block check
    for(int i=ini; i<end; i++)
    {
	config_pair *pair=cfg->get_pair(i);

	// EmptySelection
	if(!strcmp(STR_EMPTY_SELECTION, pair->get_key())) ;

	// AddRule/DelRule
	else if(!strcmp(STR_ADD_RULE, pair->get_key()) || !strcmp(STR_DEL_RULE, pair->get_key()))
	    i=cfg->skip_block(i)-1;

	// AddClass/DelClass
	else if(!strcmp(STR_ADD_CLASS, pair->get_key()) || !strcmp(STR_DEL_CLASS, pair->get_key()))
	    i=cfg->skip_block(i)-1;

	// Marks
	else if(!strcmp(STR_PRIVATE_MEMBER_MARK, pair->get_key())) set_mark(MD_MARK_PRIVATE_MEMBER, pair->get_value());
	else if(!strcmp(STR_STATUS_MEMBER_MARK, pair->get_key())) set_mark(MD_MARK_STATUS_MEMBER, pair->get_value());
	else if(!strcmp(STR_PRIVATE_METHOD_MARK, pair->get_key())) set_mark(MD_MARK_PRIVATE_METHOD, pair->get_value());
	else if(!strcmp(STR_INTERFACE_METHOD_MARK, pair->get_key())) set_mark(MD_MARK_INTERFACE_METHOD, pair->get_value());

	else if(!strcmp(STR_ATTR_PREFIX, pair->get_key())) set_mark(MD_MARK_ATTR_PREFIX, pair->get_value());
	else if(!strcmp(STR_ATTR_SEPARATOR, pair->get_key())) set_mark(MD_MARK_ATTR_SEPARATOR, pair->get_value());
	else if(!strcmp(STR_ATTR_START, pair->get_key())) set_mark(MD_MARK_ATTR_START, pair->get_value());
	else if(!strcmp(STR_ATTR_END, pair->get_key())) set_mark(MD_MARK_ATTR_END, pair->get_value());
	else if(!strcmp(STR_ATTR_NOT, pair->get_key())) set_mark(MD_MARK_ATTR_NOT, pair->get_value());
	else if(!strcmp(STR_ATTR_SELECTION, pair->get_key())) set_mark(MD_MARK_ATTR_SELECTION, pair->get_value());
	else if(!strcmp(STR_ATTR_OFFLINE, pair->get_key())) set_mark(MD_MARK_ATTR_OFFLINE, pair->get_value());

	else
	{
	    const char *valid_keys[]={STR_EMPTY_SELECTION, STR_ADD_RULE, STR_DEL_RULE, STR_ADD_CLASS, STR_DEL_CLASS,
				      STR_PRIVATE_MEMBER_MARK, STR_STATUS_MEMBER_MARK, STR_PRIVATE_METHOD_MARK,
				      STR_INTERFACE_METHOD_MARK, STR_ATTR_PREFIX, STR_ATTR_SEPARATOR, STR_ATTR_START,
				      STR_ATTR_END, STR_ATTR_NOT, STR_ATTR_SELECTION, STR_ATTR_OFFLINE, NULL};
	    return cfg->error_invalid_key(i, valid_keys);
	}
    }
    return true;
}

bool metadata::selection()
{
    // get all bases, base's off is used to selection purposes
    dwarf_base *base=dw->analyze_get_bases();
    int n_base=dw->analyze_get_n_base();

    // search selection section
    int ini, end;
    if(!cfg->search_block((char*)STR_SELECTION, NULL, &ini, &end)) {ini=0; end=-1;} else ini++;

    // reset bases
    for(int i=0; i<n_base; i++) base[i].bit.selected=base[i].bit.pattern_match=0;

    // init selection / add all named symbols (non-artificial and with non-artificial parents)
    if(end<0 || ini>=cfg->get_n_pair() || strcmp(STR_EMPTY_SELECTION, cfg->get_pair(ini)->get_key()))
	for(int i=0; i<n_base; i++)
	    if(base[i].i_name>=0 && !base[i].bit.artificial &&
	       (base[i].i_parent<0 || !base[base[i].i_parent].bit.artificial)) base[i].bit.selected=1;

    // loop over section (to make real selection)
    for(int i=ini; i<end; i++)
    {
	config_pair *pair=cfg->get_pair(i);
	int del;

	// EmptySelection
	if(!strcmp(STR_EMPTY_SELECTION, pair->get_key()))
	{
	    if(i!=ini) return cfg->error_invalid_position(i, "beginning of block");
	    if(!cfg->check_type(i, CONFIG_PAIR_VARIABLE)) return false;
	    for(int j=0; j<n_base; j++) base[j].bit.selected=0;
	}

	// AddRule/DelRule
	else if(!(del=strcmp(STR_ADD_RULE, pair->get_key())) || !strcmp(STR_DEL_RULE, pair->get_key()))
	{
	    if(!cfg->check_type(i, CONFIG_PAIR_BLOCK)) return false;
	    char *file=NULL, *name=NULL, *comment=NULL, *tag=NULL;
	    int level=pair->get_level();
	    while(1)
	    {
		i++;
		pair=cfg->get_pair(i);
		if(pair->get_level()<=level) break;
		if(!strcmp(STR_FILE, pair->get_key())) file=pair->get_value();
		else if(!strcmp(STR_NAME, pair->get_key())) name=pair->get_value();
		else if(!strcmp(STR_COMMENT, pair->get_key())) comment=pair->get_value();
		else if(!strcmp(STR_TAG, pair->get_key())) tag=pair->get_value();
		else
		{
		    const char *valid_keys[]={STR_FILE, STR_NAME, STR_COMMENT, STR_TAG, NULL};
		    return cfg->error_invalid_key(i, valid_keys);
		}
	    }
	    if(!selection_rule(!del, file, name, tag, comment)) return false;
	    i--;
	}

	// AddClass/DelClass
	else if(!(del=strcmp(STR_ADD_CLASS, pair->get_key())) || !strcmp(STR_DEL_CLASS, pair->get_key()))
	{
	    if(!cfg->check_valued_variable(i)) return false;
	    if(!selection_rule(!del, NULL/*file*/, pair->get_value(), (char*)"^structure_type$|^class_type$", NULL/*comment*/)) return false;
	}
    }

    // use base attribute ("select")
    for(int i=0; i<n_base; i++)
    {
	if(!base[i].bit.selected && source::has_attr(dw->get_doc()->string(base[i].i_attr), mark[MD_MARK_ATTR_SELECTION]))
	{
	    selection_select_recur(i, true);
	    selection_select_parents(i, true);
	}
	else if(base[i].bit.selected && source::has_neg_attr(dw->get_doc()->string(base[i].i_attr), mark[MD_MARK_ATTR_SELECTION]))
	    selection_select_recur(i, false);
    }

    return true;
}

bool metadata::selection_rule(int add, char *file, char *name, char *tag, char *comm)
{
    dwarf_base *base=dw->analyze_get_bases();
    int n_base=dw->analyze_get_n_base();
    string_index *doc=dw->get_doc();

    // compile regexes
    int error_regex=0;
    char *failed_regex=NULL;
    regex_t file_regex, name_regex, tag_regex, comm_regex;
    if(file && (error_regex=regcomp(&file_regex, file, REG_EXTENDED))) {failed_regex=file; goto error_file;}
    if(name && (error_regex=regcomp(&name_regex, name, REG_EXTENDED))) {failed_regex=name; goto error_name;}
    if(tag && (error_regex=regcomp(&tag_regex, tag, REG_EXTENDED))) {failed_regex=tag; goto error_tag;}
    if(comm && (error_regex=regcomp(&comm_regex, comm, REG_EXTENDED))) {failed_regex=comm; goto error_comm;}

    for(int i=0; i<n_base; i++)
    {
	if(base[i].bit.artificial) continue;

	if((add && !base[i].bit.selected) || (!add && base[i].bit.selected))
	{
	    // check the regex, all must have match
	    if(file && regexec(&file_regex, (base[i].i_source<0)?"":doc->string(base[i].i_source), 0, NULL, 0)) continue;
	    if(name && regexec(&name_regex, (base[i].i_name<0)?"":doc->string(base[i].i_name), 0, NULL, 0)) continue;
	    if(tag && regexec(&tag_regex, dwarf::entity_tag_string(base[i].type), 0, NULL, 0)) continue;
	    if(comm)
	    {
		char *commentary;
		if(base[i].i_source<0 || base[i].line<0 ||
		   !(commentary=src->comment(base[i].i_source, base[i].line)) ||
		   regexec(&comm_regex, commentary, 0, NULL, 0)) continue;
	    }

	    selection_select_recur(i, add);
	}
    }

    if(comm) regfree(&comm_regex);
error_comm:
    if(tag) regfree(&tag_regex);
error_tag:
    if(name) regfree(&name_regex);
error_name:
    if(file) regfree(&file_regex);
error_file:
    if(failed_regex) ERROR_R0("The regex %s failed (error=%d)", failed_regex, error_regex);
    return true;
}

bool metadata::selection_select_recur(int i, bool selected)
{
    dwarf_base *base=dw->analyze_get_bases();
    base[i].bit.selected=selected;
    for(int j=0; j<base[i].n_child; j++)
	if(!selection_select_recur(base[i].i_child[j], selected))
	    return false;
    return true;
}

bool metadata::selection_select_parents(int i, bool selected)
{
    dwarf_base *base=dw->analyze_get_bases();
    while((i=base[i].i_parent)>=0) base[i].bit.selected=selected;
    return true;
}

void metadata::dump_selection(const char *filename)
{
    FILE *arch=stdout;
    if(filename && !(arch=fopen(filename, "w"))) MSG_R("%s: dump selection: %s", filename, strerror(errno));

    // header
    if(arch==stdout) fflush(stderr);
    fprintf(arch, "Metadata selection: bases\n");

    dwarf_base *base=dw->analyze_get_bases();
    int n_base=dw->analyze_get_n_base();

    // listing
    int n=0;
    for(int i=0; i<n_base; i++)
    {
	if(base[i].bit.selected)
	{
	    if(!(n&0xf)) fprintf(arch, "\t");
	    fprintf(arch, "%6d", i);
	    n++;
	    if(!(n&0xf)) fprintf(arch, "\n");
	}
    }
    if(n&0xf) fprintf(arch, "\n");

    // detailed listing
    dump_selection_detailed(arch);

    if(arch==stdout) fflush(stdout); else fclose(arch);
}

void metadata::dump_selection_detailed(FILE *arch)
{
    dwarf_base *base=dw->analyze_get_bases();
    int n_base=dw->analyze_get_n_base();

    fprintf(arch, "==== BEGIN: Metadata selection detailed ====\n");
    for(int i=0; i<n_base; i++)
	if(base[i].bit.selected)
	{
	    dw->analyze_dump_arch(arch, i, 1/*init level*/, -1/*recur child*/, 2/*recur type*/);
	    fprintf(arch, "\n");
	}
    fprintf(arch, "==== END: Metadata selection detailed ====\n");
}

bool metadata::pattern_extract_from_cfg()
{
    // search matching section
    int ini, end;
    if(!cfg->search_block((char*)STR_MATCHING, NULL, &ini, &end) || end<=ini+1)
	return cfg->error_no_section(STR_MATCHING);
    ini++;

    // first pass: count type blocks
    n_typedefs=0;
    for(int i=ini; i<end; i++)
    {
	config_pair *pair=cfg->get_pair(i);
	if((!strcmp(STR_TYPE, pair->get_key()) && pair->get_type()==CONFIG_PAIR_BLOCK) ||
	   !strcmp(STR_TYPEDEF, pair->get_key()))
	{
	    int j=util::inc_vector(pattern, n_pattern, max_pattern, INC_PATTERN);
	    pattern[j].level=-3;
	}
    }

    // second pass to configuration file to locate relevant info, except patterns
    for(int i=ini; i<end; i++)
    {
	config_pair *pair=cfg->get_pair(i);

	if(!strcmp(STR_TYPEDEF, pair->get_key()))
	{
	    if(!cfg->check_valued_block(i)) return false;
	    int j=n_typedefs++;
	    pattern[j].level=-1;
	    pattern[j].id=pair->get_value();
	    if(!pattern_from_config(j, i, 0/*no pattern tags allowed*/)) return false;
	    i=cfg->skip_block(i)-1;
	}
	else if(!strcmp(STR_PATTERN, pair->get_key()) || !strcmp(STR_COMPONENT, pair->get_key()))
	{
	    // wait until second pass
	    if(pair->get_type()==CONFIG_PAIR_BLOCK) i=cfg->skip_block(i)-1;
	}
	else
	{
	    const char *valid_keys[]={STR_TYPEDEF, STR_PATTERN, STR_COMPONENT, NULL};
	    return cfg->error_invalid_key(i, valid_keys);
	}
    }

    // third pass: now extract patterns
    int base_level=cfg->get_pair(ini)->get_level();
    for(int i=ini; i<end; i++)
    {
	config_pair *pair=cfg->get_pair(i);

	if(!strcmp(STR_PATTERN, pair->get_key()))
	{
	    if(!cfg->check_valued(i)) return false;
	    if(pair->get_type()==CONFIG_PAIR_BLOCK)
	    {
		// block style, definition
		int j=util::inc_vector(pattern, n_pattern, max_pattern, INC_PATTERN);
		pattern[j].level=pair->get_level()-base_level;
		pattern[j].id=pair->get_value();
		if(!pattern_from_config(j, i, 1/* pattern tags allowed*/)) return false;
	    }
	    else
	    {
		// variable style: find from typedefs
		int j=util::inc_vector(pattern, n_pattern, max_pattern, INC_PATTERN);
		memset(&pattern[j], 0, sizeof(metadata_pattern));
		pattern[j].level=pair->get_level()-base_level;
		pattern[j].n_components=-2; // redirect
		pattern[j].size=-1;

		int k;
		for(k=0; k<n_pattern; k++)
		    if(pattern[k].level==-1 && pattern[k].id && !strcmp(pair->get_value(), pattern[k].id))
		    {
			pattern[j].i_type=k;
			break;
		    }
		if(k==n_pattern)
		    MSG_R0("%s:%d: unknown type \"%s\", missing TypeDef?",
			   cfg->get_filename(), pair->get_line(), pair->get_value());
	    }
	}
	else if(!strcmp(STR_COMPONENT, pair->get_key()))
	{
	    if(!cfg->check_valued_block(i)) return false;
	    int j=util::inc_vector(pattern, n_pattern, max_pattern, INC_PATTERN);
	    pattern[j].level=pair->get_level()-base_level;
	    pattern[j].id=pair->get_value();
	    if(!pattern_from_config(j, i, 0/* pattern tags allowed*/)) return false;
	    pattern[j].n_components=0;
	}
    }
    return true;
}

bool metadata::pattern_from_config(int i_pattern, int i_cfg, int tag_pattern_allowed)
{
    metadata_pattern &p=pattern[i_pattern];

    // init
    p.tag=p.name=p.encoding=p.attr=NULL;
    p.size=p.i_type=p.n_components=-1;
    p.regex_uses=0;
    p.type_recur=0;
    p.reserved=0;

    int level=cfg->get_pair(i_cfg)->get_level();
    while(1)
    {
	config_pair *pair;
	if(++i_cfg>=cfg->get_n_pair() || (pair=cfg->get_pair(i_cfg))->get_level()<=level) break;
	if(pair->get_level()>level+1) continue;

	if(!strcmp(STR_TAG, pair->get_key())) // tag
	{
	    if(!cfg->check_valued_variable(i_cfg)) return false;
	    p.tag=pair->get_value();
	}
	else if(!strcmp(STR_NAME, pair->get_key())) // name
	{
	    if(!cfg->check_valued_variable(i_cfg)) return false;
	    p.name=pair->get_value();
	}
	else if(!strcmp(STR_ENCODING, pair->get_key())) // encoding
	{
	    if(!cfg->check_valued_variable(i_cfg)) return false;
	    p.encoding=pair->get_value();
	}
	else if(!strcmp(STR_ATTR, pair->get_key())) // attribute
	{
	    if(!cfg->check_valued_variable(i_cfg)) return false;
	    p.attr=pair->get_value();
	}
	else if(!strcmp(STR_SIZE, pair->get_key())) // size
	{
	    if(!cfg->check_valued_variable(i_cfg)) return false;
	    p.size=strtol(pair->get_value(), NULL, 0);
	}
	else if(!strcmp(STR_TYPE, pair->get_key())) // type
	{
	    if(pair->get_type()==CONFIG_PAIR_BLOCK)
	    {
		int j=n_typedefs++;
		pattern[j].level=-1;
		pattern[j].id=pair->get_value();
		if(!pattern_from_config(j, i_cfg, 0/* pattern tags allowed*/)) return false;
		i_cfg=cfg->skip_block(i_cfg)-1;
		p.i_type=j;
	    }
	    else
	    {
		if(!cfg->check_valued(i_cfg)) return false;
		// find from typedefs
		int j;
		for(j=0; j<n_pattern; j++)
		    if(pattern[j].level==-1 && pattern[j].id && !strcmp(pair->get_value(), pattern[j].id))
		    {
			p.i_type=j;
			break;
		    }
		if(j==n_pattern)
		    MSG_R0("%s:%d: unknown type \"%s\", missing TypeDef?",
			   cfg->get_filename(), pair->get_line(), pair->get_value());
	    }
	}
	else if(!strcmp(STR_PATTERN, pair->get_key())) // pattern
	{
	    if(!tag_pattern_allowed) return cfg->error_invalid_key(i_cfg);
	    if(pair->get_type()==CONFIG_PAIR_BLOCK) i_cfg=cfg->skip_block(i_cfg)-1;
	}
	else if(!strcmp(STR_COMPONENT, pair->get_key())) // component
	{
	    if(!tag_pattern_allowed) return cfg->error_invalid_key(i_cfg);

	    if(!cfg->check_type(i_cfg, CONFIG_PAIR_BLOCK)) return false;
	    if(p.n_components<0) p.n_components=1;
	    else p.n_components++;
	}
	else if(!strcmp(STR_TYPE_RECUR, pair->get_key())) // type_recur
	{
	    if(!cfg->check_unvalued_variable(i_cfg)) return false;
	    p.type_recur=1;
	}
	else
	{
	    const char *valid_keys[]={STR_TAG, STR_NAME, STR_ENCODING, STR_SIZE, STR_TYPE, STR_PATTERN,
				      STR_COMPONENT, STR_TYPE_RECUR, STR_ATTR, NULL};
	    return cfg->error_invalid_key(i_cfg, valid_keys);
	}
    }
    return true;
}

bool metadata::pattern_check(int i)
{
    if(i<0) i=n_typedefs;
    if(i>=n_pattern) return 1; // no patterns!
    int level=pattern[i].level, level_prev=1<<20;
    bool dev=true;
    int *list, n_list, max_list;
    util::ctor_vector(list, n_list, max_list);

    // recursively extract blocks of patterns
    while(i<n_pattern && pattern[i].level>=level)
    {
	if(level_prev==level && pattern[i].level==level+1 && pattern[i-1].n_components<0)
	    // begin of new block (like a class with its own children)
	    dev&=pattern_check(i);
	else if(pattern[i].level==level && pattern[i].n_components<0)
	{
	    // add this to list
	    int j=util::inc_vector(list, n_list, max_list, INC_PATTERN);
	    list[j]=(pattern[i].n_components==-1)?i:pattern[i].i_type;
	}
	level_prev=pattern[i].level;
	i++;
    }

    // check block
    for(i=0; i<n_list; i++)
	for(int j=i+1; j<n_list; j++)
	{
	    if(!pattern_check_restrictiveness(list[i], list[j]))
	    {
		// error
		fprintf(stderr, "Pattern %d is after pattern %d and is more restrictive\n", list[j], list[i]);
		dump_pattern(list[i]);
		dump_pattern(list[j]);
		dev=false;
	    }
	}

    util::dtor_vector(list, n_list, max_list);
    return dev;
}

bool metadata::pattern_check_restrictiveness(int i, int j)
{
    // i should be more restrictive than j
    metadata_pattern &pi=pattern[i];
    metadata_pattern &pj=pattern[j];

    // check if they are comparable
    if((pi.tag && pj.tag && strcmp(pi.tag, pj.tag)) ||
       (pi.name && pj.name && strcmp(pi.name, pj.name)) ||
       (pi.encoding && pj.encoding && strcmp(pi.encoding, pj.encoding)) ||
       (pi.attr && pj.attr && strcmp(pi.attr, pj.attr)) ||
       (pi.size>=0 && pj.size>=0 && pi.size!=pj.size) ||
       (pi.i_type>=0 && pj.i_type>=0 && pi.i_type!=pj.i_type &&
	pattern_check_restrictiveness(pi.i_type, pj.i_type))) return true; // not comparable

    // check restrictiveness on i
    if((pi.tag && !pj.tag) ||
       (pi.name && !pj.name) ||
       (pi.encoding && !pj.encoding) ||
       (pi.attr && !pj.attr) ||
       (pi.size>=0 && pj.size<0) ||
       (pi.i_type>=0 && pj.i_type<0)) return true; // some aspect of i is more restrictive

    // check restrictiveness on j
    if((!pi.tag && pj.tag) ||
       (!pi.name && pj.name) ||
       (!pi.encoding && pj.encoding) ||
       (!pi.attr && pj.attr) ||
       (pi.size<0 && pj.size>=0) ||
       (pi.i_type<0 && pj.i_type>=0) ||
       (pi.i_type>=0 && pj.i_type>=0 && !pattern_check_restrictiveness(pi.i_type, pj.i_type))) return false;

    return true;
}

void metadata::dump_pattern(int i, FILE *arch)
{
    fprintf(arch, "%3d:\tL%d C%d %s:\n", i, pattern[i].level, pattern[i].n_components, pattern[i].id);
    if(pattern[i].tag) fprintf(arch, "\t\tTag:      %s\n", pattern[i].tag);
    if(pattern[i].name) fprintf(arch, "\t\tName:     %s\n", pattern[i].name);
    if(pattern[i].encoding) fprintf(arch, "\t\tEncoding: %s\n", pattern[i].encoding);
    if(pattern[i].attr) fprintf(arch, "\t\tAttrib. : %s\n", pattern[i].attr);
    if(pattern[i].size>=0) fprintf(arch, "\t\tSize:     %d\n", pattern[i].size);
    if(pattern[i].i_type>=0) fprintf(arch, "\t\tType:     %d\n", pattern[i].i_type);
    if(pattern[i].type_recur) fprintf(arch, "\t\tTypeRecur\n");
}

void metadata::dump_patterns(char *filename)
{
    FILE *arch=stdout;
    if(filename && !(arch=fopen(filename, "w"))) MSG_R("%s: dump patterns: %s", filename, strerror(errno));
    if(arch==stdout) fflush(stderr);

    fprintf(arch, "Patterns extracted from config file:\nNumber of typedefs: %d\n", n_typedefs);
    for(int i=0; i<n_pattern; i++) dump_pattern(i, arch);

    if(arch==stdout) fflush(stdout); else fclose(arch);
}

bool metadata::pattern_match_metadata(int i_base, int i_pattern)
{
    dwarf_base *base=dw->analyze_get_bases();
    int n_base=dw->analyze_get_n_base();
    string_index *doc=dw->get_doc();

    int ini, end;
    if(i_base<0) {ini=0; end=n_base;} else {ini=i_base; end=i_base+1;}

    int ini_pattern, end_pattern;
    if(i_pattern<0) {ini_pattern=n_typedefs; end_pattern=n_pattern;} else {ini_pattern=i_pattern; end_pattern=i_pattern+1;}

    // loop over level 0 patterns
    for(int j=ini_pattern; j<end_pattern; j++)
    {
	metadata_pattern *p=&pattern[j];
	if(p->level>0) continue;
	int jj=j;

	if(p->n_components==-2) p=&pattern[jj=p->i_type]; // redirect
	if(p->n_components>=0)
	{
	    ERROR("Components not allowed at level 0");
	    continue;
	}

	// prepare pattern
	if(!pattern_precalculate(jj)) return false;

	// extract selected bases
	for(int i=ini; i<end; i++)
	{
	    // this patterns are only for first level bases
	    if(base[i].level!=base[ini].level) continue;

	    if((i_base>=0 || base[i].bit.selected) && base[i].bit.pattern_match<=0)
	    {
		// base selected and not extracted, try to match pattern
		if(pattern_match(i, jj))
		{
		    // mark matched
		    base[i].i_function=doc->search_add_string(pattern[jj].id);

		    // make type recursion
		    if(!pattern_match_type_recursion(i, jj)) ERROR("L>0 type recursion");

		    // make child recursion
		    if(!pattern_match_metadata_recur(i, jj)) ERROR("L>0 metadata extraction");
		}
	    }
	}

	// free current pattern
	if(!pattern_free(jj)) return false;
    }

    for(int i=ini; i<end; i++)
    {
	if((i_base>=0 || base[i].bit.selected) && base[i].bit.pattern_match<=0)
	{
	    fflush(stdout);
	    ERROR("No pattern for base: %d", i);
	    if(opts->verbo>0) dw->analyze_dump(NULL/*stdout*/, i/*from*/, 1/*init_level*/, -1/*child*/, 2/*type*/);
	}
    }

    return true;
}

bool metadata::pattern_match_metadata_recur(int i_base, int i_pattern)
{
    dwarf_base *base=dw->analyze_get_bases();

    // children of base
    if(base[i_base].n_child)
    {
	string_index *doc=dw->get_doc();

	// calculate pattern scope
	int ini=i_pattern+1, end=i_pattern+1;
	while(end<n_pattern && pattern[end].level>pattern[i_pattern].level) end++;
	if(end<=ini)
	{
	    ERROR("Base %d has children but there are NO patterns inside %d to analyze them", i_base, i_pattern);
	    if(opts->verbo>0) dw->analyze_dump(NULL/*stdout*/, i_base/*from*/, 1/*init_level*/, -1/*child*/, 2/*type*/);
	    return false;
	}

	// class/struct member/method selection
	int is_class=pattern_match_select_class_children(i_base);

	// allow matching against parent pattern in case of class/struct/union
	if(is_class) ini--;

	// loop over level >0 patterns
	for(int j=ini; j<end; j++)
	{
	    metadata_pattern *p=&pattern[j];
	    if(p->level!=pattern[i_pattern].level+1 && (!is_class || j!=ini)) continue;
	    int jj=j;

	    if(p->n_components==-2) p=&pattern[jj=p->i_type]; // redirect

	    // prepare pattern
	    if(!pattern_precalculate(jj)) return false;

	    if(p->n_components<0)
	    {
		// no components
		for(int i=0; i<base[i_base].n_child; i++)
		{
		    dwarf_base &b=base[base[i_base].i_child[i]];
		    if(b.bit.pattern_match<=0 && (!is_class || b.bit.selected))
		    {
			// base not extracted, match patterns
			if(pattern_match(base[i_base].i_child[i], jj))
			{
			    // mark matched
			    b.i_function=doc->search_add_string(pattern[jj].id);

			    // make type recursion
			    if(!pattern_match_type_recursion(base[i_base].i_child[i], jj)) ERROR("L>0 type recursion");

			    // make child recursion
			    if(!pattern_match_metadata_recur(base[i_base].i_child[i], jj)) ERROR("L>0 metadata extraction");
			}
		    }
		}
	    }
	    else if(p->n_components>0)
	    {
		// multiple components
		for(int i=0; i<=base[i_base].n_child-p->n_components; i++)
		{
		    int k;
		    int old_ini_name=-1, old_end_name=-1;
		    dwarf_base *old_b=NULL;
		    for(k=0; k<p->n_components; k++)
		    {
			dwarf_base *b=&base[base[i_base].i_child[i+k]];
			if(b->bit.pattern_match>0 || (is_class && !b->bit.selected)) break;

			// match component
			int ini_name, end_name;
			if(!pattern_match(base[i_base].i_child[i+k], jj+k+1, &ini_name, &end_name) || ini_name<0 || end_name<0) break;
			if(k)
			{
			    if(old_end_name-old_ini_name!=end_name-ini_name ||
			       memcmp(doc->string(old_b->i_name)+old_ini_name, doc->string(b->i_name)+ini_name, end_name-ini_name)) break;
			}
			old_ini_name=ini_name;
			old_end_name=end_name;
			old_b=b;
		    }
		    if(k==p->n_components)
		    {
			// all components match consecutive bases
			for(k=0; k<p->n_components; k++)
			{
			    dwarf_base &b=base[base[i_base].i_child[i+k]];

			    // mark extracted
			    b.i_function=doc->search_add_string(pattern[jj].id);

			    // make type recursion
			    if(!pattern_match_type_recursion(base[i_base].i_child[i+k], jj+k+1)) ERROR("L>0 type recursion with components");

			    // no recursion possible (?)
			}
		    }
		}
	    }
	    else ERROR("internal: number of components = 0");

	    // free current pattern
	    if(!pattern_free(jj)) return false;
	}

	// warn about un-matched metadata
	for(int i=0; i<base[i_base].n_child; i++)
	{
	    dwarf_base &b=base[base[i_base].i_child[i]];
	    if(b.bit.pattern_match<=0 && (!is_class || b.bit.selected))
	    {
		fflush(stdout);
		ERROR("No pattern for base: %d", base[i_base].i_child[i]);
		if(opts->verbo>0)
		{
		    dw->analyze_dump(NULL/*stdout*/, base[i_base].i_child[i]/*from*/, 1/*init_level*/, -1/*child*/, 2/*type*/);
		    printf("Parent:\n");
		    dw->analyze_dump(NULL/*stdout*/, base[base[i_base].i_child[i]].i_parent/*from*/, 1/*init_level*/, -1/*child*/, 2/*type*/);
		}
	    }
	}
    }
    return true;
}

bool metadata::pattern_match_type_recursion(int i_base, int i_pattern, int *i_deep_recur)
{
    metadata_pattern &p=pattern[i_pattern];
    dwarf_base &b=*dw->analyze_get_base(i_base);
    bool dev=true;

    // If i_type_recur is NULL, the base b, has just been matched with the pattern p.
    // If there is a TypeRecur in the p type hierarchy, then b.bit.pattern_match, is the number of indirections
    // For instance, if p.type_recur, then b.bit_pattern_match=1, and recursion will be done over b.i_subtype base.

    if(i_deep_recur) *i_deep_recur=-1;

    if(p.type_recur)
    {
	if(b.i_subtype<0)
	{
	    if(b.type==DW_TAG_subprogram || b.type==DW_TAG_subroutine_type || // allowed w/o subtype: ie. void dump();
	       b.type==DW_TAG_typedef) // allowed w/o subtype: ie. typedef void _IO_lock_t;
	    {
		b.bit.pattern_match=0x7f;
		return true;
	    }

	    fflush(stdout);
	    ERROR("TypeRecur activated but base (%d) has no subtype", i_base);
	    fflush(stderr);
	    dw->analyze_dump(NULL, i_base, 1/*level*/, -1/*child_recur*/, 2/*type_recur*/);
	    dump_pattern(i_pattern);
	    return false;
	}

	// if named type in pattern, only match against that pattern
	int i_pattern_recur;
	if(p.i_type>=0 && pattern[p.i_type].id) i_pattern_recur=p.i_type; else i_pattern_recur=-1;

	if((dev&=pattern_match_metadata(b.i_subtype, i_pattern_recur)))
	{
	    if(i_deep_recur) *i_deep_recur=1;
	    if(b.bit.pattern_match>1) ERROR("Internal: re-matched");
	    b.bit.pattern_match=1;
	}
    }
    else
    {
	int deep=-1;
	if(p.i_type>=0 && b.i_subtype>=0) dev&=pattern_match_type_recursion(b.i_subtype, p.i_type, &deep);
	if(dev)
	{
	    if(i_deep_recur)
	    {
		// intermediate
		if(deep>0) *i_deep_recur=deep+1; else *i_deep_recur=-1; // continue counting deep or indicating no recursion
		if(!b.bit.pattern_match) b.bit.pattern_match=-1; // mark as intermediate used
	    }
	    else
	    {
		// this is the base just matched
		if(deep>0) b.bit.pattern_match=deep+1; // mark deep
		else b.bit.pattern_match=0x7f; // mark as no recursion
	    }
	}
    }
    return dev;
}

bool metadata::pattern_match(int i_base, int i_pattern, int *ini_name, int *end_name)
{
    metadata_pattern &p=pattern[i_pattern];
    dwarf_base &b=*dw->analyze_get_base(i_base);
    string_index *doc=dw->get_doc();

    regmatch_t pmatch[2];

    if(p.tag && regexec(&p.regex_tag, dwarf::entity_tag_string(b.type), 0, NULL, 0)) return false;
    if(p.name && (b.i_name<0 || regexec(&p.regex_name, doc->string(b.i_name), 2, pmatch, 0))) return false;
    if(p.encoding && (b.bit.value_meaning!=DW_VALUE_ENCODING ||
		      regexec(&p.regex_encoding, dwarf::entity_encoding_string(b.value.encoding), 0, NULL, 0))) return false;
    if(p.attr && (b.i_attr<0 || regexec(&p.regex_attr, doc->string(b.i_attr), 2, pmatch, 0))) return false;
    if(p.size>=0 && b.size!=p.size) return false;
    if(p.i_type>=0 && (b.i_subtype<0 || !pattern_match(b.i_subtype, p.i_type))) return false;

    if(p.name)
    {
	if(ini_name) *ini_name=pmatch[1].rm_so;
	if(end_name) *end_name=pmatch[1].rm_eo;
    }
    else
    {
	if(ini_name) *ini_name=-1;
	if(end_name) *end_name=-1;
    }
    return true;
}

void metadata::pattern_unmatch_dump(dwarf_base *b, int &counter, FILE *arch, int ref)
{
    // print unmatched bases
    if(arch)
    {
	string_index *doc=dw->get_doc();
	dwarf_base *base=dw->analyze_get_bases();

	// unmanaged type
	char unmng_type[N_BUFFER>>1];
	if(ref<0) snprintf(unmng_type, N_BUFFER>>1, "%s", doc->string(base[b->i_subtype].i_function));
	else snprintf(unmng_type, N_BUFFER>>1, "REF#%d", ref);

	if(!counter++) fprintf(arch, "%4s %-16s %-30s %-18s %s:%s\n",
			       "####", "BASE", "NAME", "UNMNG_TYPE", "FILE", "LINE");
	fprintf(arch, "%4d %-16s %-30s %-18s %s:%d\n",
		counter,
		dwarf::entity_tag_string(b->type),
		b->i_name>=0?doc->string(b->i_name):"<noname>",
		unmng_type,
		b->i_source>=0?doc->string(b->i_source):"<nosource>",
		b->line);
    }
}

bool metadata::pattern_unmatch_recur(int i, int &counter, FILE *arch, int ref)
{
    bool dev=true;
    dwarf_base *base=dw->analyze_get_bases();

    base[i].bit.pattern_match=-1;
    for(int j=0; j<dw->analyze_get_n_base(); j++)
    {
	int i_parent;
	dwarf_base *b=&base[j];
	if(b->bit.pattern_match>0 && b->i_subtype==i)
	{
	    switch(b->type)
	    {
	    case DW_TAG_member:
	    case DW_TAG_subprogram:
	    case DW_TAG_variable:
		// this base is of unmanageable type (must unmatch it, but warn it)
		b->bit.pattern_match=0; // remove completely function or member
		pattern_unmatch_dump(b, counter, arch, ref);
		break;
	    case DW_TAG_formal_parameter:
		// unmatch father
		pattern_unmatch_dump(b, counter, arch, ref);
		b=&base[i_parent=b->i_parent];
		b->bit.pattern_match=0; // remove completely function
		pattern_unmatch_dump(b, counter, arch, counter);
		dev&=pattern_unmatch_recur(i_parent, counter, arch, counter);
		break;
	    case DW_TAG_const_type:
	    case DW_TAG_reference_type:
	    case DW_TAG_pointer_type:
	    case DW_TAG_subroutine_type:
	    case DW_TAG_array_type:
	    case DW_TAG_typedef:
		b->bit.pattern_match=-1;
		pattern_unmatch_dump(b, counter, arch, ref);
		dev&=pattern_unmatch_recur(j, counter, arch, counter);
		break;
	    default:
		ERROR("TODO: impossible type in unknown place: %s", dwarf::entity_tag_string(b->type));
	    	dw->analyze_dump(NULL/*stdout*/, j/*from*/, 1/*init_level*/, -1/*child*/, 2/*type*/);
	    }
	}
    }
    return dev;
}

bool metadata::pattern_unmatch_impossible_metadata(int verbo, char *filename)
{
    FILE *arch=NULL;
    if(verbo>1) arch=stdout;
    if(filename && !(arch=fopen(filename, "w"))) MSG("%s: pattern unmatch: %s", filename, strerror(errno));

    const char *impossible[]={"void_pointer", "void_const_pointer", NULL};

    dwarf_base *base=dw->analyze_get_bases();
    string_index *doc=dw->get_doc();
    bool dev=true;

    // search in all bases
    int counter=0;
    for(int k=0; impossible[k]; k++)
    {
	int i_impossible;
	if((i_impossible=doc->search_string(const_cast<char*>(impossible[k])))<0) continue;

	for(int i=0; i<dw->analyze_get_n_base(); i++)
	{
	    dwarf_base &b=base[i];
	    if(b.bit.pattern_match>0 && b.i_function==i_impossible)
		// an unmanageable type is matched, search who is using it
		dev&=pattern_unmatch_recur(i, counter, arch);
	}
    }

    if(arch && arch!=stdout) fclose(arch);
    return dev;
}

bool metadata::pattern_precalculate(int i)
{
    metadata_pattern &p=pattern[i];
    char *failed_regex=NULL;

    if(!p.regex_uses)
    {
	if(p.tag && regcomp(&p.regex_tag, p.tag, REG_EXTENDED)) {failed_regex=p.tag; goto error_tag;}
	if(p.name && regcomp(&p.regex_name, p.name, REG_EXTENDED)) {failed_regex=p.name; goto error_name;}
	if(p.encoding && regcomp(&p.regex_encoding, p.encoding, REG_EXTENDED)) {failed_regex=p.encoding; goto error_encoding;}
	if(p.attr && regcomp(&p.regex_attr, p.attr, REG_EXTENDED)) {failed_regex=p.attr; goto error_attr;}
    }
    p.regex_uses++;
    if(p.i_type>=0 && !pattern_precalculate(p.i_type)) goto error_recursion;
    for(int j=0; j<p.n_components; j++) if(!pattern_precalculate(i+1+j)) goto error_recursion;
    return true;

error_recursion:
    if(p.attr) regfree(&p.regex_attr);
error_attr:
    if(p.encoding) regfree(&p.regex_encoding);
error_encoding:
    if(p.name) regfree(&p.regex_name);
error_name:
    if(p.tag) regfree(&p.regex_tag);
error_tag:

    if(failed_regex) ERROR("The regular expression \"%s\", failed", failed_regex);
    return false;
}

bool metadata::pattern_free(int i)
{
    metadata_pattern &p=pattern[i];
    for(int j=0; j<p.n_components; j++) pattern_free(i+1+j);
    if(p.i_type>=0) pattern_free(p.i_type);
    p.regex_uses--;
    if(!p.regex_uses)
    {
	if(p.attr) regfree(&p.regex_attr);
	if(p.encoding) regfree(&p.regex_encoding);
	if(p.name) regfree(&p.regex_name);
	if(p.tag) regfree(&p.regex_tag);
    }
    return true;
}

bool metadata::pattern_match_select_class_children(int i_base)
{
    dwarf_base *base=dw->analyze_get_bases();
    bool is_class=false;
    if(base[i_base].type==DW_TAG_class_type || base[i_base].type==DW_TAG_structure_type ||
       base[i_base].type==DW_TAG_union_type)
    {
	string_index *doc=dw->get_doc();
	is_class=true;
	int mark_lines[MD_MARK_INTERFACE_METHOD+1];
	int line_max=-1;
	if(base[i_base].i_source>=0)
	{
	    int line_min=0x7fffffff;
	    for(int i=-1; i<base[i_base].n_child; i++)
	    {
		dwarf_base *b;
		if(i<0) b=&base[i_base]; else b=&base[base[i_base].i_child[i]];
		if(b->line>=0 && b->i_source==base[i_base].i_source)
		{
		    if(line_min>b->line) line_min=b->line;
		    if(line_max<b->line) line_max=b->line;
		}
		else
		{
		    /* NOTE: gcc dwarf workaround

		       In some gcc versions DW_TAG_decl_* attributes seem to be wrong
		       (when including virtual methods). In this cases, instead of
		       declaration, these attributes hold the method definition
		       location.

		       This is a "manual" attempt to find true declaration locations.
		       The consequences of failing to do it are:
		         - Wrong method matching (include private methods or exclude public ones)
			 - Wrong method documentation/attributes from C++ comments

		       There's absolutely no intention to reinvent anything or to
		       reimplement gcc. This is not intended to work on ofuscated code...
		     */
		    if(!gcc_need_to_find_decls)
		    {
			gcc_need_to_find_decls++;
			MSG("warning: due to a gcc error, need to search declaration locations manually");
		    }

		    if(b->type==DW_TAG_subprogram && !b->bit.artificial && b->i_name>=0)
		    {
			string_index *methods=src->locate_class_method(base[i_base].i_name, base[i_base].i_source, base[i_base].line, b->i_name);
			if(methods && methods->n_string())
			{
			    // take lines into account
			    for(int j=0; j<methods->n_string(); j++)
			    {
				int line=strtol(methods->i_string(0), NULL, 16);
				src->add_feature_line(base[i_base].i_source, line);
				if(line_min>line) line_min=line;
				if(line_max<line) line_max=line;
			    }

			    if(/* TODO: check polymorphism*/1) //methods->n_string()==1)
			    {
				// no polymorphism here, just take proto line
				b->line=strtol(methods->i_string(0), NULL, 16);
				b->i_source=base[i_base].i_source;
			    }
			    else
				ERROR("TODO: polymorphism searching location of declaration: %s", doc->string(b->i_name));
			}
			else ERROR("cannot find real location of declaration for: %s", doc->string(b->i_name));

			if(methods) delete methods;
		    }
		}
	    }
	    if(line_max>=0) line_max++;

	    // search comments
	    for(int i=0; i<=MD_MARK_INTERFACE_METHOD; i++)
		if(!mark[i] || (mark_lines[i]=src->match_regex(base[i_base].i_source, mark[i], line_min, line_max))<0)
		    mark_lines[i]=BIG_LINE;
	}
	else
	    for(int i=0; i<=MD_MARK_INTERFACE_METHOD; i++) mark_lines[i]=BIG_LINE;

	// unselect all
	bool select=false, neg_select=false;
	for(int i=0; i<base[i_base].n_child; i++)
	{
	    int ib=base[i_base].i_child[i];
	    dwarf_base &b=base[ib];
	    if(b.type==DW_TAG_subprogram) selection_select_recur(ib, false);
	    else b.bit.selected=0;

	    // check ~select attr
	    if(b.i_attr>=0)
	    {
		if(!select && source::has_attr(doc->string(b.i_attr), mark[MD_MARK_ATTR_SELECTION])) select=true;
		if(!neg_select && source::has_neg_attr(doc->string(b.i_attr), mark[MD_MARK_ATTR_SELECTION])) neg_select=true;
	    }
	}

	// first try with DocAttrSelection algorithm over the class/struct
	char *attr;
	bool inverse; // if true, activate all except ~select
	if(neg_select && !select) inverse=true; else inverse=false;
	for(int i=0; i<base[i_base].n_child; i++)
	{
	    int ib=base[i_base].i_child[i];
	    dwarf_base &b=base[ib];
	    if((b.type==DW_TAG_member || b.type==DW_TAG_variable) && base[i_base].i_source>=0)
	    {
		// do NOT select artificial members (like virtual tables)
		if(b.bit.artificial) continue;

		// if source file does not correspond with the class base source file, then do not select
		// see NOTE: gcc dwarf workaround
		if(b.i_source!=base[i_base].i_source) continue;

		// select attribute
		if(!inverse)
		{
		    if((attr=doc->string(b.i_attr)) && source::has_attr(attr, mark[MD_MARK_ATTR_SELECTION]))
			b.bit.selected=1;
		}
		else
		{
		    if(!(attr=doc->string(b.i_attr)) || !source::has_neg_attr(attr, mark[MD_MARK_ATTR_SELECTION]))
			b.bit.selected=1;
		}
	    }
	    else if(b.type==DW_TAG_subprogram && base[i_base].i_source>=0)
	    {
		// do NOT select artificial methods
		if(b.bit.artificial) continue;

		// if source file does not correspond with the class base source file, then do not select
		// see NOTE: gcc dwarf workaround
		if(b.i_source!=base[i_base].i_source) continue;

		// select empty ctor and dtor
		if(b.i_name>=0 && (b.bit.dtor || (b.bit.ctor && b.n_child==1)))
		{
		    selection_select_recur(ib, true);
		    continue;
		}

		// select attribute
		if(!inverse)
		{
		    if((attr=doc->string(b.i_attr)) && source::has_attr(attr, mark[MD_MARK_ATTR_SELECTION]))
			selection_select_recur(ib, true);
		}
		else
		{
		    if(!(attr=doc->string(b.i_attr)) || !source::has_neg_attr(attr, mark[MD_MARK_ATTR_SELECTION]))
			selection_select_recur(ib, true);
		}
	    }
	    else
		// select rest of things
		b.bit.selected=1;
	}

	// now set selection bit on childs
	for(int i=0; !select && !neg_select && i<base[i_base].n_child; i++)
	{
	    int ib=base[i_base].i_child[i];
	    dwarf_base &b=base[ib];
	    if((b.type==DW_TAG_member || b.type==DW_TAG_variable) && base[i_base].i_source>=0)
	    {
		// do NOT select artificial members (like virtual tables)
		if(b.bit.artificial) continue;

		// if source file does not correspond with the class base source file, then do not select
		// see NOTE: gcc dwarf workaround
		if(b.i_source!=base[i_base].i_source) continue;

		// update comment lines
		if(mark_lines[MD_MARK_PRIVATE_MEMBER]<mark_lines[MD_MARK_STATUS_MEMBER])
		{
		    if(mark_lines[MD_MARK_STATUS_MEMBER]<b.line &&
		       (mark_lines[MD_MARK_PRIVATE_MEMBER]=
			src->match_regex(base[i_base].i_source, mark[MD_MARK_PRIVATE_MEMBER], b.line, line_max))<0)
			mark_lines[MD_MARK_PRIVATE_MEMBER]=BIG_LINE;
		}
		else
		{
		    if(mark_lines[MD_MARK_PRIVATE_MEMBER]<b.line &&
		       (mark_lines[MD_MARK_STATUS_MEMBER]=
			src->match_regex(base[i_base].i_source, mark[MD_MARK_STATUS_MEMBER], b.line, line_max))<0)
			mark_lines[MD_MARK_STATUS_MEMBER]=BIG_LINE;
		}

		// now line is not greater than both PRIV and STAT
		if(b.line>mark_lines[MD_MARK_PRIVATE_MEMBER]) b.bit.selected=0; else b.bit.selected=1;
	    }
	    else if(b.type==DW_TAG_subprogram && base[i_base].i_source>=0)
	    {
		// do NOT select artificial methods
		if(b.bit.artificial) continue;

		// if source file does not correspond with the class base source file, then do not select
		// see NOTE: gcc dwarf workaround
		if(b.i_source!=base[i_base].i_source) continue;

		// select empty ctor and dtor
		if(b.i_name>=0 && (b.bit.dtor || (b.bit.ctor && b.n_child==1)))
		{
		    selection_select_recur(ib, true);
		    continue;
		}

		// update comment lines
		if(mark_lines[MD_MARK_PRIVATE_METHOD]<mark_lines[MD_MARK_INTERFACE_METHOD])
		{
		    if(mark_lines[MD_MARK_INTERFACE_METHOD]<b.line &&
		       (mark_lines[MD_MARK_PRIVATE_METHOD]=
			src->match_regex(base[i_base].i_source, mark[MD_MARK_PRIVATE_METHOD], b.line, line_max))<0)
			mark_lines[MD_MARK_PRIVATE_METHOD]=BIG_LINE;
		}
		else
		{
		    if(mark_lines[MD_MARK_PRIVATE_METHOD]<b.line &&
		       (mark_lines[MD_MARK_INTERFACE_METHOD]=
			src->match_regex(base[i_base].i_source, mark[MD_MARK_INTERFACE_METHOD], b.line, line_max))<0)
			mark_lines[MD_MARK_INTERFACE_METHOD]=BIG_LINE;
		}

		// now line is not greater than both PRIV and INTERF
		selection_select_recur(ib, b.line<=mark_lines[MD_MARK_PRIVATE_METHOD]);
	    }
	    else
		// select rest of things
		b.bit.selected=1;
	}
    }
    return is_class;
}

bool metadata::generate_output(char *output, char *elf_name, char *modules_path, int verbo)
{
    // search generation section
    int ini, end;
    if(!cfg->search_block((char*)STR_GENERATION, NULL, &ini, &end) || end<=ini+1)
	return cfg->error_no_section(STR_GENERATION);
    ini++;

    // string index for file names
    string_index file_str;

    // loop over pass blocks
    bool dev=true;
    int n_repetitions=1;
    pass=0;
    while(dev && cfg->search_block((char*)STR_PASS, NULL, &ini, &end, ini))
    {
	ini++;

	// construct elf_derived
	const char *remove_extension[]={
	    "\\.so\\.[0-9]\\.[0-9]\\.[0-9]$",
	    "\\.so\\.[0-9]$",
	    "\\.so$",
	    "\\.o$",
	    "\\.a$",
	    "\\.la$",
	    "\\.lo$",
	    NULL
	};

	char elf_derived[N_BUFFER];
	snprintf(elf_derived, N_BUFFER, "%s", elf_name?elf_name:"");
	for(int j=0; remove_extension[j]; j++) string::regex_subst(remove_extension[j], NULL, elf_derived, N_BUFFER);
	char *elf_basename;
	if(strchr(elf_derived, '/')) elf_basename=strrchr(elf_derived, '/')+1; else elf_basename=elf_derived;

	// construct substitution expressions
	const char *subst[]={
	    "\\$\\(prefix\\)",       STR(PREFIX),
	    "\\$\\(generators\\)",   STR(PREFIX)"/lib/intromit/generators",
	    "\\$\\(user_output\\)",  output,
	    "\\$\\(elf_derived\\)",  elf_derived,
	    "\\$\\(elf_basename\\)", elf_basename,
	    NULL};

	// analyze pass
	for(int i=ini; i<end; i++)
	{
	    config_pair *pair=cfg->get_pair(i);
	    if(!strcmp(STR_MODULE, pair->get_key()))
	    {
		if(!cfg->check_valued_variable(i)) dev=false;
		else
		{
		    // create module name
		    char module[N_BUFFER], *module_=module;
		    snprintf(module, N_BUFFER, "%s", pair->get_value());
		    for(int j=0; subst[j]; j+=2) string::regex_subst(subst[j], subst[j+1], module, N_BUFFER);
		    while(*module_=='|' || isspace(*module_)) module_++;
		    if(strchr(module_, '|')) *strchr(module_, '|')=0;
		    if(!strlen(module_)) {dev=false; MSG("%s:%d: no module name obtained from {%s} expression",
							 cfg->get_filename(), pair->get_line(), pair->get_value());}
		    else
		    {
			int j=util::inc_vector(mod, n_mod, max_mod, INC_MODULES);
			mod[j]=NULL;

			// first search in modules_path
			char *mp=modules_path;
			while(mp)
			{
			    // create dirname from path list
			    char dirname[N_BUFFER];
			    int n_dirname;
			    strncpy(dirname, mp, N_BUFFER-1);
			    dirname[N_BUFFER-1]=0;

			    // concat basename of module_
			    char *colon=strchr(mp, ':');
			    if(colon) n_dirname=(int)(colon-mp); else n_dirname=strlen(dirname);
			    if(n_dirname && dirname[n_dirname-1]=='/') n_dirname--;
			    snprintf(dirname+n_dirname, N_BUFFER-n_dirname, "/%s", basename(module_));

			    // try to dlopen library
			    if((mod[j]=dlopen(dirname, RTLD_NOW)))
			    {
				if(verbo>0) MSG("using plug-in: %s", dirname);
				break;
			    }

			    // next path in list
			    (mp=colon) && mp++;
			}

			// open with dynamic linker config file original name
			if(!mod[j])
			{
			    if(!(mod[j]=dlopen(module_, RTLD_NOW))) {dev=false; MSG("cannot dlopen %s", dlerror());}
			    else if(verbo>0) MSG("using plug-in: %s", module_);
			}
		    }
		}
	    }
	    else if(!strcmp(STR_FUNC_PREFIX, pair->get_key()))
	    {
		if(!cfg->check_valued_variable(i)) dev=false;
		else
		{
		    // copy func prefix
		    if(prefix) free(prefix);
		    prefix=(char*)malloc((n_prefix=strlen(pair->get_value()))+N_BUFFER);
		    strcpy(prefix, pair->get_value());
		}
	    }
	    else if(!strcmp(STR_FILE, pair->get_key()))
	    {
		if(!cfg->check_valued_variable(i)) dev=false;
		else
		{
		    // create module name
		    char filename[N_BUFFER], *filename_=filename;
		    snprintf(filename, N_BUFFER, "%s", pair->get_value());
		    for(int j=0; subst[j]; j+=2) string::regex_subst(subst[j], subst[j+1], filename, N_BUFFER);
		    while(*filename_=='|' || isspace(*filename_)) filename_++;
		    if(strchr(filename_, '|')) *strchr(filename_, '|')=0;
		    if(!strlen(filename_)) {dev=false; MSG("%s:%d: no file name obtained from {%s} expression",
							   cfg->get_filename(), pair->get_line(), pair->get_value());}
		    else
		    {
			// mode: search filename in string index
			const char *mode;
			if(file_str.search_string(filename_)<0)
			{
			    file_str.search_add_string(filename_);
			    mode="w";
			}
			else
			    mode="a";

			// open file
			int j=util::inc_vector(out, n_out, max_out, INC_FILE);
			if(!(out[j]=fopen(filename_, mode)))
			{
			    dev=false;
			    MSG("cannot open %s with mode %s: %s", filename_, mode, strerror(errno));
			}
			else if(verbo>0) MSG("generating product: %s", filename_);
		    }
		}
	    }
	    else if(!strcmp(STR_REPETITIONS, pair->get_key()))
	    {
		if(!cfg->check_valued_variable(i)) dev=false;
		else n_repetitions=strtol(pair->get_value(), NULL, 0);
	    }
	    else
	    {
		int j;
		for(j=0; j<MD_FUNC_LAST; j++)
		{
		    if(!strcmp(md_func_keys[j], pair->get_key()))
		    {
			if(!cfg->check_valued_variable(i)) dev=false;
			else set_function((metadata_funcs)j, pair->get_value());
			break;
		    }
		}
		if(j==MD_FUNC_LAST)
		{
		    const char *valid_keys[]={STR_MODULE, STR_FUNC_PREFIX, STR_FILE,
					      STR_REPETITIONS, "<or any func id>", NULL};
		    cfg->error_invalid_key(i, valid_keys);
		    dev=false;
		}
	    }
	}

	// do pass
	if(dev && !dw->analyze_goto_beginning()) {dev=false; ERROR("cannot go to base tree top");}
	if(dev && functions[MD_FUNC_INIT]) generate_output_call_function(functions[MD_FUNC_INIT]);
	for(repetition=0; repetition<n_repetitions && dev; repetition++)
	{
	    if(dev && functions[MD_FUNC_INIT_PASS]) generate_output_call_function(functions[MD_FUNC_INIT_PASS]);
	    if(dev && !generate_output_pass()) {dev=false; ERROR("error with pass: %s", cfg->get_pair(ini-1)->get_value());}
	    if(dev && functions[MD_FUNC_FINISH_PASS]) generate_output_call_function(functions[MD_FUNC_FINISH_PASS]);
	    if(dev && !dw->analyze_goto_beginning()) {dev=false; ERROR("cannot go to base tree top");}
	}
	if(dev && functions[MD_FUNC_FINISH]) generate_output_call_function(functions[MD_FUNC_FINISH]);

	// close files
	for(int i=0; i<n_out; i++) if(out[i]) fclose(out[i]);
	n_out=0;

	// close modules
	for(int i=0; i<n_mod; i++) if(mod[i] && dlclose(mod[i])) ERROR("error in dlclose: %s", strerror(errno));
	n_mod=0;

	// free prefix
	if(prefix) prefix=(char*)realloc(prefix, 0);
	n_prefix=0;

	// reset functions
	reset_functions();

	// user data
	user_data=NULL;

	// go to next pass
	ini=end;
	pass++;
    }
    pass=-1;
    return dev;
}

bool metadata::generate_output_pass()
{
    string_index *doc=dw->get_doc();

    // traverse level
    do
    {
	// do base stuff
	dwarf_base *b=dw->bp();
	if(b->bit.pattern_match>0)
	{
	    if(b->i_function>=0) generate_output_call_function(doc->string(b->i_function));

	    // type
	    if(b->bit.pattern_match!=0x7f && functions[MD_FUNC_TYPE_RECUR]) generate_output_call_function(functions[MD_FUNC_TYPE_RECUR]);

	    // children
	    if(dw->analyze_get_n_child())
	    {
		if(functions[MD_FUNC_DOWN]) generate_output_call_function(functions[MD_FUNC_DOWN]);
		if(!dw->analyze_down(0)) ERROR_R0("internal error: goto into children 0");
		if(!generate_output_pass()) return false;
		if(functions[MD_FUNC_UP]) generate_output_call_function(functions[MD_FUNC_UP]);
		if(!dw->analyze_up()) ERROR_R0("internal error: goto parent");
	    }
	}

	if(functions[MD_FUNC_NEXT]) generate_output_call_function(functions[MD_FUNC_NEXT]);
    }
    while(dw->analyze_move_next_in_level());
    return true;
}

bool metadata::generate_output_call_function(char *name)
{
    // get function name
    if(prefix)
    {
	strncpy(&prefix[n_prefix], name, N_BUFFER);
	name=prefix;
    }

    // search function in all modules and call to function
    int i_mod;
    for(i_mod=-1; i_mod<n_mod; i_mod++)
    {
	if(i_mod<0 || mod[i_mod])
	{
	    void *func;
	    if((func=dlsym((i_mod<0)?NULL:mod[i_mod], name)))
	    {
		((int(*)(metadata *))func)(this);
		break;
	    }
	}
    }
    if(i_mod==n_mod) ERROR("Cannot get the function %s in the modules provided", name);
    return true;
}

string_index *metadata::get_doc()
{
    return dw->get_doc();
}
